package training;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author liangzai
 * @Description:
 */
public class J25_6_16_Training {
    //电话号码的字母组合
    public List<String> letterCombinations(String digits) {

        String[] arr = {"abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
        String[] list = new String[digits.length()];
        for(int i=0;i<digits.length();i++){
            int num = digits.charAt(i) - '0'-2;
            list[i] = arr[num];
        }


        return build(list,0,list.length-1);
    }

    public List<String> build(String[] arr, int start, int end){

        List<String> result = new ArrayList<>();
        if(start > end) return result;

        String str = arr[start];

        List<String> buildStr = build(arr,start+1,end);
        boolean flag = buildStr.size() > 0;

        for(int i=0;i<str.length();i++){
            if(flag){
                for(int j=0;j<buildStr.size();j++){
                    result.add(str.charAt(i) + buildStr.get(j));
                }
            }else{
                result.add(str.charAt(i) + "");
            }
        }

        return result;
    }
}
